package leetcode

func sortArray(nums []int) []int {
	quicksort(nums, 0, len(nums)-1)
	return nums
}

func quicksort(nums []int, left, right int) {
	if left >= right {
		return
	}
	mid := partition(nums, left, right)
	quicksort(nums, left, mid-1)
	quicksort(nums, mid+1, right)
}

func partition(nums []int, left, right int) int {
	com, l, r := nums[right], left, right-1
	for l <= r {
		for l <= r && nums[l] <= com {
			l++
		}
		for l <= r && nums[r] >= com {
			r--
		}
		if l < r {
			nums[l], nums[r] = nums[r], nums[l]
		}
	}
	nums[l], nums[right] = nums[right], nums[l]
	return l
}
